home *** CD-ROM | disk | FTP | other *** search
/ ASME's Mechanical Engine…ing Toolkit 1997 December / ASME's Mechanical Engineering Toolkit 1997 December.iso / ai / prlg195b.lzh / GRAMMAR.LZH / ATN.PRO
Text File  |  1987-12-08  |  10KB  |  385 lines
  1. /* -------------------------------------------------------------------------
  2.  
  3.     ATN.PRO    by  Eugene L. Frassetto
  4.  
  5.    -------------------------------------------------------------------------
  6.  
  7.     This is a simple, basic Augmented Transition Net for parsing an
  8.     English sentence.
  9.  
  10.     The typed sentence is converted to a list of words and a parse tree is
  11.     returned.  The parse tree will always have the infinitive form of the
  12.     verb.  e.g.
  13.       The boy hit the ball.
  14.       becomes [the,boy,hit,the,ball,.]
  15.       => [[the,boy],[hit,[the,ball]],[.]]
  16.  
  17.       The boy with the bat hit the big green ball.
  18.       becomes [the,boy,with,the,bat,hit,the,big,green,ball,.]
  19.       => [[[the,boy],[with,[the,bat]]],[hit,[the,big,green,ball]],[.]]
  20.  
  21.       Is John going?
  22.       becomes [is,john,going,with,us?]
  23.       => [[john],[[is],[to,go],[with,us]]]],[?]]
  24.  
  25.       Can John drive the red car with the big dog?
  26.       becomes [can,john,drive,the,red,car,with the big,dog,?]
  27.       => [[john],[[can],[drive,[[the,red,car],[with,[the,big,dog]]]]],[?]]
  28.  
  29.       What are cars?
  30.       becomes [what,are,cars,?]
  31.       => [[cars],[are,[what]],[?]]
  32.  
  33.         Note from Bob Morein: 
  34.           Further examples:
  35.           Where is the boy? ( wh_word, aux_verb )
  36.       Where go the boy? ( wh_word, verb )
  37.  
  38.  
  39.     The grammar for this ATN is:
  40.         S --> NP VP '.'         (declarative)
  41.         S --> VP '!'            (imperative - you understood)
  42.         S --> AUX_VERB NP ING_VP '?'    (yes-no question)
  43.         S --> MODAL NP VP '?'        (yes-no question)
  44.         S --> WH_WORD AUX_VERB NP '?'    (wh question)
  45.         S --> WH_WORD VERB '?'        (wh question)
  46.            NP --> PROPER_NOUN
  47.            NP --> PRONOUN
  48.            NP --> DETERMINER NOUN
  49.            NP --> DETERMINER ADJs NOUN
  50.            NP --> NP PP
  51.          ADJs --> ADJECTIVE ADJs
  52.            PP --> PREPOSITION NP
  53.            VP --> VERB
  54.            VP --> VERB NP
  55.            VP --> VERB PP
  56.  
  57.     Using the second example above, the parse tree is:
  58.  
  59.                        S
  60.                        |
  61.          +-------------------------+---+----------------------+
  62.          |                   |              |
  63.         NP                  VP              |
  64.       +------+------+               |              |
  65.       |        |               |              |
  66.       |           PP               |              |
  67.       |        |               |              |
  68.       |       +----+---+         +-----+-----+              |
  69.       |       |        |         |         |              |
  70.      NP       |       NP         |        NP              |
  71.       |       |        |         |         |              |
  72.     +-+-+       |      +-+-+      |     +---+-+--+----+          |
  73.     |   |       |      |   |      |     |   |    |    |          |
  74.        DET NOUN   PREP     DET NOUN    VERB  DET ADJ  ADJ  NOUN  FINAL_PUNC
  75.     |   |       |      |   |      |     |   |    |    |          |
  76.   [ [ [the,boy], [with, [the,bat] ] ], [hit, [the,big,green,ball] ], [.] ]
  77.  
  78.     To start things off type 'go.'
  79.  
  80.     You will be prompted to enter a sentence.
  81.     Note from Bob Morein: You must not backspace while entering the
  82.         sentence. If you make a mistake, type a period, hit return, and
  83.         the program will process your error and then return for more 
  84.         input.
  85.  
  86.     To exit the parser type "quit." (without the quotes) when prompted
  87.     to enter a sentence.
  88.  
  89.    ------------------------------------------------------------------------- */
  90.  
  91.  
  92. go :-
  93.     repeat,
  94.         print( '  Enter a sentence.' ), nl,
  95.         read_in( P ), nl,
  96.         ( (P = [quit,.], ! );
  97.           ( ( parse( P, Tree ),
  98.               print( Tree ), nl,
  99.               fail );
  100.             ( not( parse( P, _ ) ),
  101.               print( 'Not a valid sentence.' ), nl,
  102.               fail ) ) ).
  103.  
  104. /* parse a simple declarative sentence */
  105. parse( P, Ptree ) :-
  106.     ( npp( P, Np, Rest );
  107.       np( P, Np, Rest ) ), !,
  108.     vp( Rest, Vp, [Fp] ), !,
  109.     Fp = '.', !,
  110.     Ptree = [Np, Vp, [Fp]].
  111.  
  112. /* parse an imperative sentence (insert 'you') */
  113. parse( P, Ptree ) :-
  114.     vp( P, Vp, [Fp] ), !,
  115.     ( Fp = '!';
  116.       Fp = '.'), !,
  117.     Ptree = [[you], Vp, [Fp]].
  118.  
  119. /* parse a yes-no question which starts with is, are, etc. */
  120. parse( [Aux | P], Ptree ) :-
  121.     aux_verb( Aux ), !,
  122.     np( P, Np, [First | Rest] ), !,
  123.     ing_base( First, Base ), !,
  124.     vp( [Base | Rest], Vp, [Fp] ), !,
  125.     Fp = '?', !,
  126.     Ptree = [Np, [[Aux], [to | Vp]], [Fp]].
  127.  
  128. /* parse a yes-no question which starts with can, will, etc. */
  129. parse( [Modal | P], Ptree ) :-
  130.     modal( Modal ), !,
  131.     np( P, Np, Rest ), !,
  132.     vp( Rest, Vp, [Fp] ), !,
  133.     Fp = '?', !,
  134.     Ptree = [Np, [[Modal], Vp], [Fp]].
  135.  
  136. /* ---------------------------------------------------------------------- */
  137.  
  138. /* parse a 'wh-word verb' question */
  139. parse( [Wh, Verb | Rest], Ptree ) :-
  140.     wh_word( Wh ),
  141.     verb( Verb ), !,
  142.     ( npp( Rest, Np, [Fp] );
  143.       np( Rest, Np, [Fp] ) ), !,
  144.     Fp = '?', !,
  145.     Ptree = [[Wh], [Verb, Np], [Fp]].
  146.  
  147. /* parse a 'wh-word aux_verb' question */
  148. parse( [Wh, Aux | Rest], Ptree ) :-
  149.     wh_word( Wh ),
  150.     aux_verb( Aux ), !,
  151.     ( npp( Rest, Np, [Fp] );
  152.       no( Rest, Np, [Fp] );
  153.       np( Rest, Np, [Fp] ) ), !,
  154.     Fp = '?', !,
  155.     Ptree = [Np, [Aux, [Wh]], [Fp]].
  156.  
  157.  
  158. /* ------------------------------------------------------------------------ */
  159.  
  160.  
  161. /* noun phrase containing pronoun or a proper noun */
  162. np( [Pnoun | T], [Pnoun], T ) :-
  163.     ( pnoun( Pnoun );
  164.       pronoun( Pnoun ) ),
  165.     !.
  166.  
  167. /* noun phrase with an attached prepositional phrase */
  168. npp( S, [Np, Pp], Rest ) :-
  169.     np( S, Np, Rest1 ),
  170.     pp( Rest1, Pp, Rest ),
  171.     !.
  172.  
  173. /* noun phrase with a determiner and a noun */
  174. np( [Det, Noun | T], [Det, Noun], T ) :-
  175.     s_noun( Noun, Snoun ),
  176.     det( Det ),
  177.     !.
  178.  
  179. /* noun phrase with a determiner, adjective and noun */
  180. np( [Det, Adj, Noun | T], [Det, Adj, Noun], T ) :-
  181.     det( Det ),
  182.     adj( Adj ),
  183.     s_noun( Noun, Snoun ),
  184.     !.
  185.  
  186. /* noun phrase with a det adjs and a noun */
  187. np( [Det, Adj | T], Np, Rest ) :-
  188.     det( Det ),
  189.     adj( Adj ),
  190.     adjs( T, Adjs, [Noun | Rest] ),
  191.     s_noun( Noun, Snoun ),
  192.     append( Adjs, [Noun], X ),
  193.     append( [Det, Adj], X, Np ),
  194.     !.
  195.  
  196. /* noun alone for special cases */
  197. no( [Noun | Rest], [Noun], Rest ) :-
  198.     s_noun( Noun, _ ),
  199.     !.
  200.  
  201. no( [Adj, Noun | Rest], [Adj, Noun], Rest) :-
  202.     adj( Adj ), !,
  203.     s_noun( Noun, _ ),
  204.     !.
  205.  
  206. adjs( [Adj | T], Adjs, T ) :-
  207.     not( adj( Adj ) ).
  208.  
  209. adjs( [Adj | T], Adjs, T ) :-
  210.     adj( Adj ),
  211.     adjs( T, X, Rest ),
  212.     append( [Adj], X, Adjs ).
  213.  
  214. /* prepositional phrase */
  215. pp( [Prep | T], [Prep, Np], Rest ) :-
  216.     prep( Prep ),
  217.     np( T, Np, Rest ),
  218.     !.
  219.  
  220. /* verb phrase containing a verb and a noun phrase */
  221. vp( [Verb | T], [Verb, Np], Rest ) :-
  222.     verb( Verb ),
  223.     ( npp( T, Np, Rest );
  224.       np( T, Np, Rest ) ),
  225.     !.
  226.  
  227. /* verb phrase with just a verb */
  228. vp( [Verb | Rest], [Verb], Rest ) :-
  229.     verb( Verb ),
  230.     !.
  231.  
  232. /* verb phrase with a verb and either a np, a np and pp or a pp by itself
  233.    this is for the yes-no questions */
  234. vp( [Verb | T], [Verb, Np], Rest ) :-
  235.     verb( Verb ),
  236.     ( npp( T, Np, Rest );
  237.       np( T, Np, Rest );
  238.       pp( T, Np, Rest ) ),
  239.     !.
  240.  
  241. /* --------------------------------------------- */
  242. /*                         */
  243. /*       word morphology predicates         */
  244. /*                         */
  245. /* --------------------------------------------- */
  246. /* get base of an ing verb */
  247. /* verb with double consonant - hitting => hit */
  248. ing_base( Test, Base ) :-
  249.     name( Test, X ),
  250.     reverse( X, [_,_,_,_ | Y]),
  251.     reverse( Y, Z ),
  252.     name( Base, Z ),
  253.     verb( Base ).
  254.  
  255. /* regular verb - going => go */
  256. ing_base( Test, Base ) :-
  257.     name( Test, X ),
  258.     reverse( X, [_,_,_ | Y]),
  259.     reverse( Y, Z ),
  260.     name( Base, Z ),
  261.     verb( Base ).
  262.  
  263. /* verb ending with 'e' - driving => drive */
  264. ing_base( Test, Base ) :-
  265.     name( Test, X ),
  266.     reverse( X, [_,_,_ | Y]),
  267.     reverse( [101 | Y], Z ),
  268.     name( Base, Z ),
  269.     verb( Base ).
  270.  
  271. /* get the singular of a plural noun */
  272. /* cars => car, car => car, walk => FALSE */
  273. s_noun( P, S ) :-
  274.     noun( P ), !,
  275.     S = P.
  276.  
  277. s_noun( P, S ) :-
  278.     name( P, X ),
  279.     reverse( X, [_ | Y] ),
  280.     reverse( Y, Z ),
  281.     name( S, Z ), !,
  282.     noun( S ),
  283.     !.
  284.  
  285.  
  286. /* the dictionary */
  287. pnoun( john ).
  288. pnoun( mary ).
  289. pronoun( he ).
  290. pronoun( him ).
  291. pronoun( she ).
  292. pronoun( her ).
  293. pronoun( i ).
  294. pronoun( me ).
  295. pronoun( we ).
  296. pronoun( us ).
  297. pronoun( you ).
  298. noun( boy ).
  299. noun( ball ).
  300. noun( bat ).
  301. noun( dog ).
  302. noun( car ).
  303. wh_word( who ).
  304. wh_word( what ).
  305. wh_word( when ).
  306. wh_word( where ).
  307. det( a ).
  308. det( an ).
  309. det( the ).
  310. adj( big ).
  311. adj( small ).
  312. adj( green ).
  313. adj( red ).
  314. adj( long ).
  315. adj( short ).
  316. prep( with ).
  317. prep( in ).
  318. prep( to ).
  319. verb( hit ).
  320. verb( go ).
  321. verb( run ).
  322. verb( swim ).
  323. verb( drive ).
  324. verb( walk ).
  325. aux_verb( is ).
  326. aux_verb( are ).
  327. modal( will ).
  328. modal( can ).
  329. final_punc( '.' ).
  330. final_punc( '?' ).
  331. final_punc( '!' ).
  332.  
  333.  
  334. /* ------------------------------------------------------ *
  335.  *                              *
  336.  *        misc. aux and helper predicates          *
  337.  *                              *
  338.  *  ----------------------------------------------------- */
  339.  
  340. /* append two lists - [a,b,c],[d,e,f] => [a,b,c,d,e,f] */
  341. append( [], AnyList, AnyList).
  342. append( [Head | Tail], List2, [Head | NewTail] ) :-
  343.     append( Tail, List2, NewTail ).
  344.  
  345. /* reverse a list - [a,b,c] => [c,b,a] */
  346. reverse([F], [F]).
  347. reverse([H | T], X) :-
  348.     reverse(T, Y),
  349.     append(Y, [H], X).
  350.  
  351. /* ---------------------------------------------------------------- *
  352.  *                                    *
  353.  *      The following code is from the file RSENT.PRO.        *
  354.  *      It inputs a sentence and returns it as a list.        *
  355.  *      (it dosen't handle backspace so type with care)           *
  356.  *                                    *
  357.  *      my thanks to its' author.                                 *
  358.  *                                    *
  359.  * ---------------------------------------------------------------- */
  360. read_in([W|Ws]) :- get0(C), readword(C,W,C1), restsent(W,C1,Ws).
  361.  
  362. restsent( W,_,[]) :- final_punc(W), !.
  363. restsent(W,C,[W1|Ws]) :- readword(C,W1,C1), restsent(W1,C1,Ws).
  364.  
  365. readword(C,W,C1) :- single_character(C), !, name(W,[C]), get0(C1).
  366. readword(C,W,C2) :-
  367.     in_word(C,NewC), !,
  368.     get0(C1),
  369.     restword(C1,Cs,C2),
  370.     name(W,[NewC|Cs]).
  371. readword(C,W,C2) :- get0(C1), readword(C1,W,C2).
  372.  
  373. restword(C,[NewC|Cs],C2) :-
  374.     in_word(C,NewC), !,
  375.     get0(C1),
  376.     restword(C1,Cs,C2).
  377. restword(C,[],C).
  378.  
  379. single_character(63).  /* ? */
  380. single_character(33).  /* ! */
  381. single_character(46).  /* . */
  382.  
  383. in_word(C,C) :- C>96, C<123.                /* a b..z */
  384. in_word(C,L) :- C>64, C<91, L is C+32.      /* A,B..Z */
  385.